package 二分查找树_BST;

/**
 * @Classname 二叉搜索树的范围和_938
 * @Description TODO
 * @Date 2020/9/13 10:32
 * @Created by xiaok
 */
public class 二叉搜索树的范围和_938 {
    /**
     * 给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
     *
     * 二叉搜索树保证具有唯一的值。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
     * 输出：32
     * 示例 2：
     *
     * 输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
     * 输出：23
             *递归终止条件：
             * 当前节点为 null 时返回 0
             * 当前节点 X < L 时则返回右子树之和
             * 当前节点 X > R 时则返回左子树之和
             * 当前节点 X >= L 且 X <= R 时则返回：当前节点值 + 左子树之和 + 右子树之和
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public int rangeSumBST(TreeNode root, int L, int R) {
        if( root ==null) return 0;
        return root.val>=L && root.val<=R ? root.val+rangeSumBST(root.left,L,R)+rangeSumBST(root.right,L,R):
                rangeSumBST(root.left,L,R)+rangeSumBST(root.right,L,R);
    }
}
